<?php
/**
 * User: LRZ
 * Date: 2020/1/13
 * Time: 14:29
 */

/**
 *  169.多数元素
 *
 *  标签：位运算、数组、分治算法
 *
 *  给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
 *  你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 *  示例 1:
 *      输入: [3,2,3]
 *      输出: 3
 *
 *  示例 2:
 *      输入: [2,2,1,1,1,2,2]
 *      输出: 2
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/majority-element
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$nums = [3, 2, 3];
$res  = majorityElement($nums);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function majorityElement($nums)
{
    $count     = 0;
    $candidate = null;
    foreach ($nums as $v) {
        if ($count === 0) {
            $candidate = $v;
        }
        ($candidate === $v) ? $count++ : $count--;
    }
    return $candidate;
}